The Computational Geometry Algorithms Library (CGAL) offers data
structures and algorithms like triangulations (2D constrained
triangulations and Delaunay triangulations in 2D and 3D, periodic
triangulations in 3D), Voronoi diagrams (for 2D and 3D points, 2D
additively weighted Voronoi diagrams, and segment Voronoi diagrams),
polygons (Boolean operations, offsets, straight skeleton), polyhedra
(Boolean operations), arrangements of curves and their applications
(2D and 3D envelopes, Minkowski sums), mesh generation (2D Delaunay
mesh generation and 3D surface and volume mesh generation, skin
surfaces), geometry processing (surface mesh simplification,
subdivision and parameterization, as well as estimation of local
differential properties, and approximation of ridges and umbilics),
alpha shapes, convex hull algorithms (in 2D, 3D and dD), search
structures (kd trees for nearest neighbor search, and range and
segment trees), interpolation (natural neighbor interpolation and
placement of streamlines), shape analysis, fitting, and distances
(smallest enclosing sphere of points or spheres, smallest enclosing
ellipsoid of points, principal component analysis), and kinetic data
structures.
